package main

import "container/list"

/*
 * Definition for a binary tree node.
 */
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

type CBTInserter struct {
	//用数组表示完全二叉树
	nodes []*TreeNode
}

func Constructor(root *TreeNode) CBTInserter {
	return CBTInserter{nodes: levelOrder(root)}
}

func (this *CBTInserter) Insert(val int) int {
	l := len(this.nodes)
	node := &TreeNode{Val: val}
	this.nodes = append(this.nodes, node)
	if l == 0 {
		return -1
	}
	pIdx := parent(l)
	parentNode := this.nodes[pIdx]
	if leftChild(pIdx) == l {
		parentNode.Left = node
	} else {
		parentNode.Right = node
	}
	return parentNode.Val
}

func (this *CBTInserter) Get_root() *TreeNode {
	if len(this.nodes) == 0 {
		return nil
	}
	return this.nodes[0]
}

/**
 * Your CBTInserter object will be instantiated and called as such:
 * obj := Constructor(root);
 * param_1 := obj.Insert(val);
 * param_2 := obj.Get_root();
 */
/*
	 0
	/  \
   1    2
  / \  / \
 3  4  5  6
*/

//完全二叉树父子节点索引关系
func parent(index int) int {
	return (index - 1) / 2
}

func leftChild(index int) int {
	return 2*index + 1
}

func rightChild(index int) int {
	return 2*index + 2
}

//层序遍历
func levelOrder(root *TreeNode) []*TreeNode {
	nodes := make([]*TreeNode, 0)
	queue := list.New()
	if root != nil {
		queue.PushBack(root)
	}
	for queue.Len() > 0 {
		node := queue.Remove(queue.Front()).(*TreeNode)
		nodes = append(nodes, node)
		if node.Left != nil {
			queue.PushBack(node.Left)
		}
		if node.Right != nil {
			queue.PushBack(node.Right)
		}
	}
	return nodes
}
